package com.lun.medium;

import com.lun.util.BinaryTree.TreeNode;

public class LowestCommonAncestorOfDeepestLeaves {
    
	//方法一：自己写的，用后序遍历模式
    public TreeNode lcaDeepestLeaves(TreeNode root) {
    	Object[] result = lcaDeepestLeaves(root, 0);
    	return result != null ? (TreeNode)result[0] : null;
    }
    
    private Object[] lcaDeepestLeaves(TreeNode node, int depth) {
    	if(node == null) return null;
    	
    	depth++;
    	
    	Object[] leftResult = lcaDeepestLeaves(node.left, depth);
    	Object[] rightResult = lcaDeepestLeaves(node.right, depth);
    	
    	if(leftResult == null && rightResult == null) {//叶子节点
    		return new Object[] {node, depth};
    	}else if(leftResult != null && rightResult == null){
    		return leftResult;
    	}else if(leftResult == null && rightResult != null) {
    		return rightResult;
    	}else {
    		int leftDepth = (int)leftResult[1];
    		int rightDepth = (int)rightResult[1];
    		
    		if(leftDepth > rightDepth) {
    			return leftResult; 
    		}else if(leftDepth < rightDepth) {
    			return rightResult;
    		}else {
    			leftResult[0] = node;
    			return leftResult;
    		}
    	}
    }
	
    //方法二：别人写的，用后序遍历模式
    public TreeNode lcaDeepestLeaves2(TreeNode root) {
        Pair p = getLca(root, 0);
        return p.node;
    }
    
    private Pair getLca(TreeNode root, int d) {
        if (root == null) return new Pair(null, d);
        Pair l = getLca(root.left, d + 1);
        Pair r = getLca(root.right, d + 1);
        if (l.d == r.d) {
            return new Pair(root, l.d);
        } else {
            return  l.d > r.d ? l : r;
        }
    }
    
    private class Pair {
    	TreeNode node;
    	int d;
    	Pair(TreeNode node, int d) {
    		this.node = node;
    		this.d = d;
    	}
    }
}
